1748B - Diverse Substrings - CodeForces Solution

#include <bits/stdc++.h>
/*
 * Basic Runtimes Table:
 * +-----+-----------------+
 * |  n  | Worst Algorithm |
 * +-----+-----------------+
 * | 11  | O(n!), O(n^6)   |
 * | 18  | O(2^n * n^2)    |
 * | 22  | O(2^n * n)      |
 * | 100 | O(n^4)          |
 * | 400 | O(n^3)          |
 * | 2K  | O(n^2 log n)    |
 * | 10K | O(n^2)          |
 * | 1M  | O(n log n)      |
 * +-----+-----------------+
 */
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

#define INF 100000000
#define MOD 1000000007
#define endl '\n'
#define LIST(az, bz) for (int cz = 0; cz < (int)(bz); cz++) cout << az[cz] << (cz == (int)(bz)-1 ? '\n' : ' ');

int T, N;

int main()
{
	// ios_base::sync_with_stdio(false);
	// cin.tie(NULL);
	// cout.tie(NULL);
	
	cin >> T;
	while (T--) {
		cin >> N;

		string s;
		cin >> s;

		int ans = 0;
		for (int n = 0; n < N; n++) {
			vi used(10);
			vi counts(10);

			int unique = 0, max_count = 1;
			for (int i = 0; i < 100 && n + i < N; i++) {
				int d = s[n+i] - '0';
				if (!used[d]) {
					used[d] = true;
					unique++;	
				}
				counts[d]++;
				max_count = max(max_count, counts[d]);
				if (unique >= max_count) {
					ans++;
				}
			}
		}
		
		cout << ans << endl;
	}
}